// https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/
// Created by ade on 2022/7/18.
//
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    vector<int> res;

    // 数组解法
    TreeNode *sortedListToBST1(ListNode *head) {
        while (head) {
            res.push_back(head->val);
            head = head->next;
        }
        return build(0, res.size() - 1);
    }

    TreeNode *build(int left, int right) {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode *head = new TreeNode(res[mid]);
        head->left = build(left, mid - 1);
        head->right = build(mid + 1, right);
        return head;
    }

    // 指针解法
    TreeNode *sortedListToBST(ListNode *head) {
        return build1(head, nullptr);
    }

    ListNode *getMid(ListNode *left, ListNode *right) {
        ListNode *mid = left;
        while (left && left->next != right) { // 注意的坑：left本身可能是nullptr,导致栈溢出
            ListNode *tmpNext = left->next;
            if (tmpNext) {
                mid = tmpNext;
                left = tmpNext->next;
            }
            if (!left->next) {
                break;
            }
        }
        return mid;
    }

    TreeNode *build1(ListNode *left, ListNode *right) {
        if (!left) return nullptr;
        ListNode *mid = getMid(left, right);
        TreeNode *top = new TreeNode(mid->val);
        top->left = build1(left, mid);
        top->right = build1(mid->next, right);
        return top;
    }

    ListNode *init() {
        ListNode *head1 = new ListNode(1);
        ListNode *head2 = new ListNode(2);
        ListNode *head3 = new ListNode(3);
//        ListNode * head4 = new ListNode(4);
//        ListNode * head5 = new ListNode(5);
        head1->next = head2;
        head2->next = head3;
//        head3->next = head4;
//        head4->next = head5;
        return head1;
    }

    void show(TreeNode *head) {
        if (head) {
            cout << head->val << ",";
            show(head->left);
            show(head->right);
        }
    }
};

int main() {
    Solution so;
    ListNode *head = so.init();
    auto res = so.sortedListToBST(head);
    so.show(res);
    return 0;
}